#include "stdio.h"
#include <mqoai.h>

typedef char VertexType;
typedef int EdgeType;

#define MAXVEX 9

Boolean visited[MAXVEX];

typedef struct VerTex{
    VertexType vertex[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVexs, numEdges;
}MGraph;

// 队列的结构（顺序表和链表的实现不一样，可查看之前线性结构部分）
typedef struct Queue{}*Queue;

void initQueue(Queue *Q){}
void EnQueue(Queue *Q, int i){}
void DeQueue(Queue *Q, int i){}
Boolean QueueEmpty(Queue *Q){}

void BFSTraverse(MGraph G){
    int i, j;
    Queue Q;
    for (i = 0; i < G.numVexs; i++) {
        visited[i] = FALSE;
    }
    // 初始化辅助队列
    initQueue(&Q);
    for (i = 0; i < G.numVexs; i++) {
        // 未被访问过的先访问后入队
        if(!visited[i]) {
            visited[i] = TRUE;
            printf("%c", G.vertex[i]);
            EnQueue(&Q, i);
            // 队列非空则出队，然后寻找出队结点的邻接点
            while (!QueueEmpty(&Q)) {
                DeQueue(&Q, i);
                // 邻接点边存在且未被访问过，则也访问后入队（必须判断边存在，若只判断visited数组可能会判断错误）
                for (j = 0; j < G.numVexs; j++) {
                    if(G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = TRUE;
                        printf("%c", G.vertex[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}